Binary Heaps | Data Structure | Pusan National University

structure propertystructure property(완전 이진트리여야 한다는 조건)는 마지막 레벨을 뺀 모든 레벨이 차고 마지막 레벨은 왼쪽부터 채우라고 한다.

힙 성질부모와 자식 노드 사이만 정한다. 형제끼리의 순서는 정하지 않지만 루트에는 최솟값이 온다.

최소 힙(min-heap)과 최대 힙(max-heap)부등호만 뒤집으면 루트에 최댓값이 오는 최대 힙이 된다.

인덱스 계산0부터 세면 왼쪽 자식 노드 2i + 1, 오른쪽 자식 노드 2i + 2, 부모 ⌊(i − 1)/2⌋다.

힙은 모양 조건과 힙 성질을 둘 다 지켜야 한다

네 가지 트리를 고르면 두 조건을 각각 검사한 결과와 어긋난 자리가 바뀐다. 가운데가 빈 트리는 여섯 값을, 나머지는 일곱 값을 담았다.

트리

위는 트리, 아래는 같은 트리를 레벨 순서로 담은 배열이다. 빨간 굵은 선은 부모가 자식 노드보다 커서 힙 성질을 어긴 간선이고, 빨간 점선 원과 칸은 모양 조건이 허용하지 않는 빈 자리다. 초록 원은 루트다.

힙 [5, 9, 11, 14, 18, 19, 21, 33, 17, 27]에서 인덱스 i를 바꾸면 그 칸의 부모와 두 자식 노드가 트리와 배열에서 함께 표시된다.

인덱스 i 3

초록으로 채운 원과 칸이 인덱스 i, 초록 테두리가 그 부모와 자식 노드다. 원 아래 작은 수와 칸 아래 수가 인덱스이며, 배열 위 초록 곡선이 계산으로 오가는 칸을 잇는다.

노드 수 n을 바꾸면 완전 이진트리의 모양, 높이, 자식 노드가 없는 단말 노드의 인덱스 범위가 바뀐다.

노드 수 n 10

원 안의 수는 인덱스다. 파란 원은 자식 노드가 있는 노드, 회색 원은 단말 노드이고 아래 배열에서도 같은 색으로 칠했다.